package leetcode.周赛.第249场;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/11 11:22
 * @description：https://leetcode-cn.com/contest/weekly-contest-249/problems/painting-a-grid-with-three-different-colors/
 */
public class 用三种不同颜色为网格涂色 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.colorTheGrid(5, 5));
    }

    class Solution {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int m, n;
        int count = 0;
        final int MOD = 100000007;
        public int colorTheGrid(int m, int n) {
            this.m = m;
            this.n = n;
            int[][] map = new int[m][n];
            dfs(map, 0, 0);
            return count;
        }

        private void dfs(int[][] map, int row, int col) {
            if (row >= m && col >= n) {
                count++;
                count %= MOD;
                return;
            }
            HashSet<Integer> set = new HashSet<>();
            for (int[] dir : dirs) {
                int curRow = row + dir[0];
                int curCol = col + dir[1];
                if (curRow >= 0 && curRow < m && curCol >= 0 && curCol < n && map[curRow][curCol] != 0) {
                    set.add(map[curRow][curCol]);
                }
            }
            if (set.size() == 3) return;

            for (int k = 1; k <= 3; k++) {
                if (!set.contains(k)) {
                    map[row][col] = k;
                    if (col + 1 < n) {
                        dfs(map, row, col + 1);
                    } else if (row + 1 < m){
                        dfs(map, row + 1, col);
                    } else {
                        dfs(map, row + 1, col + 1);
                    }
                }
            }

        }
    }

}
